#pragma region  【算法7 - 2】折半插入排序算法 
void B_InsertSort(datatype R[], int n)
{ // 对排序表R[1]..R[n]作折半插入排序, n是记录的个数
    for (i = 2; i <= n; i++)
    {
        R[0] = R[i]; // 保存待插入元素
        low = 1;
        high = i - 1;       // 设置初始区间
        while (low <= high) // 该循环语句完成确定插入位置
        {
            mid = (low + high) / 2;
            if (R[0].key > R[mid].key)
                low = mid + 1; // 插入位置在高半区中
            else
                high = mid - 1; // 插入位置在低半区中
        }
        for (j = i - 1; j >= high + 1; j--) // high+1为插入位置
            R[j + 1] = R[j];                // 后移元素，留出插入空位
        R[high + 1] = R[0];                 // 将元素插入
    }
}
#pragma endregion